|
Grammar theory to model symbol strings originated from work in computational linguistics aiming at understanding the structure of natural languages.〔〔〔 Through controlled grammar exploring and scoring the correctness of a sentence construct in a language by computation is achievable. Grammars are said to be generative grammars/transformational grammars if their rules are used to predict/emit words forming grammatical sentences. Probabilistic context free grammars (PCFG) have been applied in probabilistic modeling of RNA structures almost 40 years post their introduction in computational linguistics.〔〔〔〔〔 PCFGs extend context-free grammars similar to how hidden Markov models extend regular grammars. Each production is assigned a probability. The probability of a derivation (parse) is the product of the probabilities of the productions used in that derivation. These probabilities are typically computed by machine learning programs operating on large databases. A probabilistic grammar's validity is constrained by context of its training dataset. PCFGs have application in areas as diverse as natural language processing to the study the structure of RNA molecules and design of programming languages. Designing efficient PCFGs has to weigh factors of scalability and generality. Issues such as grammar ambiguity need to be resolved. The grammar design influences results accuracy. Grammar parsing algorithms have various time and memory requirements. ==Definitions== Derivation: The process of recursive generation of strings from a grammar. Parsing: Finding a valid derivation using an automaton. Parse Tree: The alignment of the grammar to a sequence. An example of a parser for PCFG grammars is the pushdown automaton. The algorithm parses grammar nonterminals from left to right in a stack-like manner. This brute-force approach is not very efficient. In RNA secondary structure prediction variants of the Cocke–Younger–Kasami (CYK) algorithm (CYK) algorithm provide more efficient alternatives to grammar parsing than pushdown automata.〔 Another example of a PCFG parser is the Stanford Statistical Parser which has been trained using Treebank,. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Stochastic context-free grammar」の詳細全文を読む スポンサード リンク
|